1. Field of the Invention
The present invention relates to a livelock preventative measure in multiprocessor environments.
2. Related Art
Livelock conditions occur in multiprocessor environments when two agents vie for data at the same memory address. Such conditions occur infrequently but, when they occur, they prevent the system from making forward progress. Control of the data is swapped between the two processors while each waits for the other to complete its operation. Because neither processor is able to complete its respective operation, neither processor makes forward progress.
A processor communicates with external memories and devices via an external bus. In multi-agent systems, a plurality of processor devices may be connected to the external bus. An "agent" may be considered any device, memory or processor that is connected to the external bus.
A transaction is a set of bus activities related to a single bus request. For example, in the known Pentium.RTM. Pro processor, commercially available from Intel Corporation, a transaction proceeds through six phases:
Arbitration, in which an agent becomes the bus owner, PA1 Request, in which a request is made identifying an address, PA1 Error, in which errors in the request phase are identified, PA1 Snoop, in which cache coherency checks are made, PA1 Response, in which the failure or success of the transaction is indicated, and PA1 Data, in which data may be transferred.
Other processors may support transactions in other ways.
In multiple agent systems, the external bus may be a pipelined bus. In a pipelined bus, several transactions may progress simultaneously provided the transactions are in mutually different phases. Thus, a first transaction may be started at the arbitration phase while a snoop response of a second transaction is being generated and data is transferred for a third transaction. However, a given transaction generally does not "pass" another in the pipeline.
Cache coherency is an important feature of a multiple agent system. If an agent is to operate on data, it must confirm that the data it will read is the most current copy of the data that is available. In such multiple agent systems, several agents may operate on data from a single address. Oftentimes when a first agent desires to operate on data at an address, a second agent may have cached a copy of the data that is more current than the copy resident in an external memory. The first agent should read the data from the second agent rather than from the external memory. Without a means to coordinate among agents, an agent may perform a data operation on stale data.
In the snoop phase, the agents coordinate to maintain cache coherency. In the snoop phase, each of the agents reports whether it possesses an unmodified copy of the data or whether it possesses a modified ("dirty") copy of the data at the requested address. In the Pentium.RTM. Pro, an agent indicates that it possesses an unmodified copy of the data by asserting a HIT# pin in a snoop response. An agent indicates that it possesses a dirty copy of the requested data by asserting a HITM# pin. If dirty data exists, it is more current than the copy in memory. Thus, dirty data will be read by an agent from the agent possessing the dirty copy. Non-dirty data is read by an agent from memory. Only an agent that possesses a copy of data at the requested address drives a snoop response; if an agent does not possess such a copy, it generates no snoop response.
A snoop response is expected from all agents at a predetermined point in a transaction. Occasionally, an agent cannot respond to another agent's request before the period closes. When this occurs, the agent may generate a "snoop stall" response that indicates that the requesting agent must wait longer for snoop results. In the Pentium.RTM. Pro processor, the snoop stall signal occurs when an agent toggles both outputs HIT# and HITM# from high to low in unison.
A livelock condition occurs when two agents snoop to the same address almost simultaneously in an attempt to read or manipulate data at that address. To process an instruction, a first agent snoops to an address specified in the instruction. Initially, no other agent owns data at that address and the first agent reads the data in from the external memory. Before the first agent can manipulate the requested data, a second agent requests data at the same address. The first agent indicates its ownership of the contested data and cedes ownership to the second agent. The first agent does not complete the instruction that caused it to read in the contested data. In fact, the first agent may not have read the data--the second agent's request for the contested data may have divested the first agent's ownership before the first agent read it at the data phase of its earlier request.
After the first agent cedes control, it determines which instruction to process next. It identifies the original instruction. Accordingly, the first agent requests the data that it just conveyed away. The second agent responds to the request by indicating its ownership of the address and conveys the data back to the first agent. Of course, the second agent was unable to complete its desired operation on the data. The first and second agents will snoop the data away from each other indefinitely, causing a livelock condition.
As is known, processors typically perform many instructions in the time that it takes to execute one bus transaction on the external bus. Some instructions may require the processor to read data via the external bus, others may not. Accordingly, wherever possible, processors schedule instructions so that, when data for a first instruction is being read to the processor, other unrelated instructions may be processed. When a livelock condition occurs, the processor typically exhausts all instructions that are unrelated to the instruction that is subject to the livelock. In this case, the processor stalls because it cannot execute the one instruction that is subject to the livelock.
Thus, there is a need in the art for a means to prevent livelock conditions in multi-agent systems.